package leetcode_周赛._2023._02;

import java.util.Arrays;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * 第 331 场周赛
 * AC_2
 *
 * @author yezh
 * @date 2023/2/5 10:34
 */
public class _05 {

    public static void main(String[] args) {
        System.out.println(Math.sqrt(100));
    }

    public long pickGifts(int[] gifts, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int gift : gifts) queue.offer(gift);
        while (k-- > 0) {
            int max = queue.poll();
            max = (int) Math.sqrt(max);
            queue.offer(max);
        }
        long ans = 0;
        for (int i = 0; i < gifts.length; i++) ans += queue.poll();
        return ans;
    }

    static final Set<Character> metaLetter = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u'));

    public int[] vowelStrings(String[] words, int[][] queries) {
        int m = words.length, n = queries.length;
        int[] prefix = new int[m + 1];
        for (int i = 0; i < m; i++) {
            if (metaLetter.contains(words[i].charAt(0)) && metaLetter.contains(words[i].charAt(words[i].length() - 1)))
                prefix[i + 1] = prefix[i] + 1;
            else prefix[i + 1] = prefix[i];
        }
        int[] ans = new int[queries.length];
        for (int i = 0; i < n; i++) {
            int l = queries[i][0], r = queries[i][1];
            ans[i] = prefix[r + 1] - prefix[l];
        }
        return ans;
    }

    /**
     * 2560. 打家劫舍 IV
     * 算法：二分查找 + 动态规划
     * 最大化最小值、最小化最大值
     * 单调性 ==> 偷的金额越大, 可以偷的房间越多, 反之越少
     * 1 <= nums[i] <= 10 ^ 9, 枚举答案
     * 使用动态规划, 算出当前枚举值可以取到的最少房间
     */
    public int minCapability(int[] nums, int k) {
        int l = 0, r = (int) 1e9;
        while (l <= r) {
            int mid = (l + r) >>> 1;
            int f0 = 0, f1 = 0;
            for (int num : nums)
                // 金额不能超过 mid
                if (num > mid) f0 = f1;
                else {
                    int tmp = f1;
                    f1 = Math.max(f0 + 1, f1);
                    f0 = tmp;
                }
            if (f1 >= k) r = mid - 1;
            else l = mid + 1;
        }
        return l;
    }

}
